import turtle, copy


class Stack:  # 栈的实现
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        if len(self.items) > 0:
            return self.items[len(self.items) - 1]
        else:
            return None

    def size(self):
        return len(self.items)


pole_width = 200
pole_height = 120   # pole_height/10 为 图像中的柱子最多能装下的盘子数


def drawPoles():  # 绘制所有的柱子
    t = turtle.Turtle()
    t.hideturtle()

    def drawpole(k):  # 画柱子
        t.up()
        t.pensize(10)
        t.speed(0)
        t.goto(pole_width * (k - 1), pole_height)
        t.down()
        t.goto(pole_width * (k - 1), -pole_height)
        t.goto(pole_width * (k - 1) - 20, -pole_height)
        t.goto(pole_width * (k - 1) + 20, -pole_height)

    for i in range(3):
        drawpole(i)


def getPoleStack():
    return [Stack() for _ in range(3)]


def initDrawPlates(n):  # 绘制盘子
    plates = [turtle.Turtle() for _ in range(n)]
    for i in range(n):
        plates[i].hideturtle()
        plates[i].up()
        plates[i].shape('square')
        plates[i].color('red')
        plates[i].shapesize(1, n - i)
        plates[i].goto(-pole_width, 10 - pole_height + 20 * i)
        plates[i].showturtle()
    return plates


def moveDisk(plates, poles, source, destination):  # poles[source]->poles[destination]
    mov = poles[source].peek()
    if mov is None:
        return
    plates[mov].speed(3)
    # 移动效果
    plates[mov].goto((source - 1) * pole_width, pole_height+50)
    plates[mov].goto((destination - 1) * pole_width, pole_height+50)
    length = poles[destination].size()  # 确定移动到底部的高度
    plates[mov].goto((destination - 1) * pole_width, 10 - pole_height + 20 * length)


def moveTower(plates, poles, n, a, b, c):
    global times
    global lst
    length = len(lst)
    if n > 1:
        oldList = copy.deepcopy(lst)
        moveTower(plates, poles, n - 1, a, c, b)
        print('第', length - n + 2, '层:(', oldList, '->', lst, ')')

        oldList = copy.deepcopy(lst)
        print('\033[31m [', times, ']\t', 'Move', chr(n + ord('A') - 1), 'from', a + 1, '->', c + 1, '\033[0m')
        moveDisk(plates, poles, a, c)
        poles[c].push(poles[a].pop())
        times += 1
        lst[length - n] = c + 1
        print("================切换分支===============================")
        print('第', length - n + 2, '层:(', oldList, '->', lst, ')')
        print("================切换分支===============================")

        oldList = copy.deepcopy(lst)
        moveTower(plates, poles, n - 1, b, a, c)
        print('第', length - n + 2, '层:(', oldList, '->', lst, ')')
        print("================回溯上一层===============================")
    elif n == 1:
        print('\033[31m [', times, ']\t', 'Move', chr(n + ord('A') - 1), 'from', a + 1, '->', c + 1, '\033[0m')
        moveDisk(plates, poles, a, c)
        poles[c].push(poles[a].pop())
        lst[length - n] = c + 1
        times += 1


times = 1  # 移动步数
lst = []  # 存储状态


def main():
    global lst
    drawPoles()  # 画柱子
    n = eval(input('盘子数量'))
    plates = initDrawPlates(n)  # 盘子列表,turtle.Turtle()绘图对象
    poles = getPoleStack()  # 柱子栈  [Stack() for _ in range(3)]
    for i in range(n):
        poles[0].push(i)
    lst = [1 for _ in range(n)]
    oldList = copy.deepcopy(lst)
    moveTower(plates, poles, n, 0, 1, 2)
    print('第', 1, '层:(', oldList, '->', lst, ')')
    turtle.done()


if __name__ == "__main__":
    main()

